This multicenter ACTG study is designed to evaluate the effect of megestrol acetate, with and without supplement of testosterone, in patients with HIV-associated wasting. Megestrol acetate is a potent appetite stimulant that has been shown to cause substantial weight gain in patients with wasting syndrome. However, the weight gain is predominantly, if not exclusively, fat. The observation that megestrol treatment results in a decrease in testosterone levels provides a possible explanation for the body composition changes that occur with this agent. Patients with HIV-associated wasting will be treated with megestrol acetate, 800 mg a day, and then randomized to receive either testosterone, 200 mg every other week, or testosterone placebo. After 12 weeks of double-blind treatment, all subjects will be eligible for combined therapy for an additional 12 weeks. Major outcomes include weight, body composition, quality of life, and monitoring for safety.